1. Field of the Invention
The present invention relates generally to processing of image data used, for example, to represent text, graphics and scanned images. More particularly, the invention relates to processing of image data by partitioning the image into a plurality of subimages.
2. State of the Art
Digitized images displayed on scanners, monitors and printers are typically quantized on a pixel-by-pixel basis and stored in memory as pixel maps, more commonly referred to as pixmaps. A pixmap is a two-dimensional array of picture elements mapped to locations of the digitized image.
To provide sufficient color range and fidelity, each pixel is typically stored in memory as a set of color coordinates which define the pixel's color location in a given color space. For example, a pixel is typically represented by its red, green and blue color component values, or by its cyan, magenta and yellow color component values. The fidelity of the color reproduction is a function of the accuracy with which each color component is represented.
Due to the increased volume of data required to represent color images, effort has been directed to decreasing the memory requirements associated with color data pixmaps to provide more efficient transmission and storage of the image. A known technique for enhancing processing speed is to divide the input frame of image data into a plurality of subdivided, or partitioned areas, so that each subdivided area can be individually processed. However, a common problem encountered when an input frame of image data is divided into blocks is that pixels of the subdivided images are not properly transformed to an output space wherein the original image is to be reconstructed.
For example, FIG. 3a illustrates an image represented as a frame of image data. This frame of image data is shown divided into a plurality of subdivided images which can be individually processed. By dividing the frame of image data to a plurality of subdivided images, memory requirements associated with processing components can be reduced since only a single subdivided image need be stored in memory at any given time during processing.
However, it is often desirable to transform the image represented by the input frame of image data in FIG. 3a to a different scale or resolution for output (e.g., output on a display or printer). Further, it is often desirable that the image represented by the frame of input image data in FIG. 3a be skewed or rotated for subsequent output. For example, it may be desirable to scale a 300 pixel by 300 pixel input frame of image data to a printer output frame of 1000 pixels by 1000 pixels. Because 1000 is not an integer multiple of 300, a direct mapping of each pixel in the input frame to a set number of pixels in the output frame is not possible. As a result, some pixels in the output frame may be left unmapped thereby creating an appearance of holes in an output image which is produced using the output image data.
In addition, it may be desired to skew or rotate the input frame of image data to produce a rotated image at the output device. Those skilled in the art will appreciate that when the plurality of subimages illustrated in FIG. 3a are skewed or rotated, some additional pixel locations in the output frame of image data will not be mapped to any subimage of the input frame of image data. That is, a rectangular subimage which encompasses a 3.times.3 pixel array of the input frame, when skewed or rotated by a fixed angle, will no longer be defined by a rectangular pixel array in the output frame. See, for example, FIG. 2a wherein an image is represented by a plurality of pixels which form a square. However, once the image is skewed, it is no longer represented by a plurality of pixels which represent a square in the output frame buffer. FIG. 2b shows a similar example for plural subimages which are skewed. Again, pixels which are not mapped to any of the subimages in the input frame of image data will appear as holes in the output image when it is displayed or printed.
Thus, computational errors, such as errors in rounding or truncation when an image is transformed, can result in an incomplete allocation, or mapping of pixels in an output frame of image data among the various subimages of the input frame of image data. If the pixel locations in an output frame buffer which stores the output image data are not accurately mapped to the various subimages of the input frame of image data, image artifacts will appear along boundaries between subimages when the original image is reconstructed, and will be readily apparent to the unaided eye.
A known technique for addressing the inaccuracies associated with processing partitioned image data is to divide the input frame of image data into several overlapping subimages so that gaps between subimages will not occur in the output frame buffer. However, such techniques do not resolve misalignments of boundary artifacts. For example, misalignments between the plurality of subimages in the output frame of image data can produce image artifacts due to the inaccurate representation of the boundaries between subimages.
Another technique for addressing the inaccuracies of transforming partitioned image data into an output frame buffer includes mapping the pixel locations between the input frame of image data and the output frame of image data to avoid boundary misalignments. Mapping techniques between an input space associated with the input frame of image data and an output space associated with the output frame of image data are of two general types: (1) those that perform image transformation from an input device space to output device space using forward mapping; and (2) those that perform image transformation from an input device space to an output device space using inverse mapping. These latter two techniques are described in a book entitled "Digital Image Warping", by George Wolberg, ISBO-8186-8944-7, 1984, pages 42-45.
Forward mapping generally refers to a mapping from an input image space to an output device space by copying each input pixel onto the output image in a frame of output image data at positions determined by X and Y mapping functions, as described for example in the aforementioned Wolberg book. Although forward mapping can efficiently map an input frame of image data to an output frame of image data, this technique suffers the drawback of having holes in the output image when reconstructed. For example, when an input image is resampled to produce an output image (e.g., scaled and/or rotated), forward mapping cannot accurately map every pixel in the output frame of image data to a particular pixel of a subimage in the input frame of image data. Rather, some pixels in the output image are left unmapped to a subimage of the input frame due, for example, to the rounding or truncation which occurs when the input image is transformed to the output space.
The inverse mapping technique is performed by computing a mapping of every output pixel to the input image. Although inverse mapping guarantees that no holes will result in the reconstructed image, this technique suffers the drawback of much slower performance because a computation must be performed for each pixel in the output frame of image data. That is, a computation is used to identify all pixels in the input frame of image data which are to be mapped to that particular output pixel.
Accordingly, it would be desirable to provide a technique for partitioning image data such that the image data can be efficiently processed in a manner whereby the reconstructed image does not include holes due to misalignment of boundary artifacts, yet which achieves performance which is equal to or better than that associated with conventional techniques such as forward mapping.